package oj;

import java.util.*;


public class Num692 {
    private class Freq {
        String word;
        int freq;

        public Freq(String word, int freq) {
            this.word = word;
            this.freq = freq;
        }
    }

    public List<String> topKFrequent(String[] words, int k) {
        //将元素存入map中
        Map<String, Integer> map = new HashMap<>();
        for (String a : words) {
            map.put(a, map.getOrDefault(a, 0) + 1);
        }
        //使用优先级队列
        PriorityQueue<Freq> queue = new PriorityQueue<>(new Comparator<Freq>() {
            @Override
            public int compare(Freq o1, Freq o2) {
                if (o1.freq == o2.freq) {
                    return o2.word.compareTo(o1.word);
                }
                return o1.freq - o2.freq;
            }
        });

        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (queue.size() < k) {
                queue.add(new Freq(entry.getKey(), entry.getValue()));
            } else {
                Freq peekFreq = queue.peek();
                if (entry.getValue() == peekFreq.freq && entry.getKey().compareTo(peekFreq.word) < 0) {
                    queue.poll();
                    queue.offer(new Freq(entry.getKey(), entry.getValue()));

                }
                if (entry.getValue() > peekFreq.freq) {
                    queue.poll();
                    queue.offer(new Freq(entry.getKey(), entry.getValue()));
                }
            }
        }

//        LinkedList<String> list = new LinkedList<>();
//        while (!queue.isEmpty()) {
//            list.addFirst(queue.poll().word);
//        }
//        return list;
        String[] ret = new String[k];
        for (int i = 0; i < k; i++) {
            ret[i] = queue.poll().word;
        }
        return reverse(ret);
    }
    public List<String> reverse(String[] ret){
        List<String> list1=new ArrayList<>();
        for (int i = ret.length-1; i >=0 ; i--) {
            list1.add(ret[i]);
        }
        return list1;
    }
}
